package day_2022_12_to_3.year2023;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author haomin
 * @date 2023/03/10 22:45
 **/
public class Day3_10_Num1590 {
    class Solution {
        public int minSubarray(int[] nums, int p) {
            int n = nums.length, minStep = n;
            // key: 前缀和(对p取模)     value: 相同前缀和对应的下标
            Map<Integer, Stack<Integer>> map = new HashMap<>(16);
            // 正序遍历，保存对p取模后前缀和的下标
            for (int i = 0, sum = 0; i < n; i++) {
                sum = (sum + nums[i]) % p;
                if (sum == 0 && minStep > n - i - 1) minStep = n - i - 1;
                map.computeIfAbsent(sum, v -> new Stack<>()).add(i);
            }
            if (minStep == 0) return minStep;
            // 倒序遍历, 找到与sum(nums[i], ..., nums[n - 1)相加的和能整除p的第一个小于i的下标
            for (int i = n - 1, sufSum = 0; i > 0; i--) {
                sufSum = (sufSum + nums[i]) % p;
                if (sufSum == 0 && minStep > i) minStep = i;
                // 不存在前缀和 + 当前后缀和 能整除p的组合
                if (!map.containsKey(p - sufSum)) continue;
                // 前缀和 + 当前后缀和 能整除p, 前缀和的下标
                Stack<Integer> preSumIdxes = map.get(p - sufSum);
                while (!preSumIdxes.isEmpty()) {
                    Integer peek = preSumIdxes.peek();
                    if (peek >= i) {
                        preSumIdxes.pop();
                    } else {
                        if (minStep > i - peek - 1) minStep = i - peek - 1;
                        break;
                    }
                }
            }
            return minStep == n ? -1 : minStep;
        }
    }
}